#!/usr/bin/env python
# -*-coding: utf-8 -*-

import os
import sys
sys.path.append(os.path.join(os.path.dirname(__file__), '..'))
import utils.rand_kit as rand_kit

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

class Tree:
    def __init__(self):
        self.head = None

    def dump(self):
        if self.head is None:
            print("No nodes")
        else:
            a = []
            out = []
            a.append(self.head)
            while len(a) != 0:
                temp = a[0]
                if temp is None:
                    out.append('-')
                else:
                    out.append(temp.data)
                    a.append(temp.left)
                    a.append(temp.right)
                a.pop(0)
            print('%s' % ','.join(str(i) for i in out))
    
    def deep(self, t):
        if t is None:
            return 0
        else:
            return self.max(self.deep(t.left), self.deep(t.right)) + 1
    
    def max(self, a, b):
        if a < b:
            return b
        else:
            return a
    
    def LL(self, t):
        l = t.left
        t.left = l.right
        l.right = t
        return l
    
    def RR(self, t):
        r = t.right
        t.right = r.left
        r.left = t
        return r

    def LR(self, t):
        t.left = self.RR(t.left)
        return self.LL(t)

    def RL(self, t):
        t.right = self.LL(t.right)
        return self.RR(t)
    
    def insert_internal(self, t, data):
        if t is None:
            t = TreeNode(data)
            return t
        else:
            if data < t.data:
                t.left = self.insert_internal(t.left, data)
            else:
                t.right = self.insert_internal(t.right, data)
            ldeep = self.deep(t.left)
            rdeep = self.deep(t.right)
            if ldeep - rdeep > 1:
                if data < t.left.data:
                    # left - left
                    t = self.LL(t)
                else:
                    # left - right
                    t = self.LR(t)
            elif rdeep - ldeep > 1:
                if data > t.right.data:
                    # right - right
                    t = self.RR(t)
                else:
                    # right - left
                    t = self.RL(t)
        return t
    
    def insert(self, data):
        self.head = self.insert_internal(self.head, data)

if __name__ == "__main__":
    tree = Tree()
    arr = rand_kit.rand_arr()
    print("The arr: %s" % ','.join(str(i) for i in arr))
    for a in arr:
        tree.insert(a)
    print("------------The tree------------")
    tree.dump()
    print("Tree height: %d" % tree.deep(tree.head))
    print("Tree left height: %d" % tree.deep(tree.head.left))
    print("Tree right height: %d" % tree.deep(tree.head.right))